1. Field of the Invention
This invention relates to high speed processing in computer servers and in computer networking and, more particularly, to devices and methods for performing interval location.
2. Description of the Related Art
The following descriptions and examples are given as background only.
Computer networking is generally recognized as the communication of packets across an interconnected network of computers. One objective of networking is to quickly forward the packets from a source to a destination. Thus, one or more forwarding devices may be placed within the network for performing such a function. As used herein, the term “forwarding devices” can be used interchangeably to refer to gateways, bridges, switches, or routers.
A forwarding device typically includes a lookup table containing a representation of at least a portion of the network topology, as well as current information about the best known paths (or “routes”) from the forwarding device to one or more destination addresses. For example, a forwarding device may store address prefixes (or “prefix entries”) and next hop identifiers in a lookup table. The prefix entries generally represent a group of destination addresses that are accessible through the forwarding device, whereas next hop identifiers represent the next device along the path to a particular destination address. Other information may be stored within the lookup table, such as the outgoing port number, paths associated with a given route, time out values and one or more statistics about each route.
When an incoming address is received by a forwarding device, the address is compared to the prefix entries stored within the lookup table. If a match occurs, the packet of information associated with the address is sent to an appropriate output port of the forwarding device. As links within the network change, routing protocols sent between forwarding devices may change the prefix entries within the corresponding lookup tables. This change will modify not only the prefix entries within the lookup table, but also the next-hop identifiers pointed to by those prefix entries. Thus, routing through the forwarding devices can be dynamically changed (i.e., updated) as links go down and come back up in various parts of the network.
The Internet Protocol (IP) is the protocol standard most widely used for packet communication to and from the Internet. Internet Protocol (IP) addresses associated with a packet generally comprise a network field (for identifying a particular network) and a host field (for identifying a particular host on that network). All hosts on the same network have the same network field but different host fields. The network field may be of arbitrary length (as in class-based addressing architectures), or may be constrained to fixed network-host field boundaries (as in classless architectures).
In addition to determining the next hop for incoming packets, some forwarding devices may be configured for solving an interval location problem. Interval location problems show up in several places in a networking system, one example of which can be seen in queue scheduling for traffic management in routers and switches. Given a set of N numbers, {k1, k2 . . . kN}, and a point, P, the interval location problem is to find the interval, i, containing the point, P, where 1≦i<N and ki≦P<ki+1. If P<k1 or P>kN, the integer values 0 and N are returned, respectively. Unfortunately, hashing cannot be used to solve the interval location problem because it is not an exact match operation.
In some cases, binary trees may be used to perform interval location using the longest-matching prefix technique. However, conventional search algorithms that use binary tree structures fail to provide an efficient solution to the interval location problem. For example, most conventional algorithms require log N operations (i.e., memory accesses) to perform an interval search, and an additional log N operations to carry out updates. This means that, if N=64K (typical number of queues in a large switch or router), approximately 16 memory accesses would be required to carry out a search or update operation. In addition to providing long search/update times, the binary tree structures used in most conventional search algorithms may include approximately 2N nodes. Considering that each node has at least two pointers (say 4 Bytes each) for a binary representation, the total space required to store the data structure may be approximately
2×64K×2×4=1 MB=8 Mb. Even though a data structure of this size may be stored within a fast SRAM with 4 ns random access time, 16 memory accesses would still require 64 ns per search operation. Such time consumption is not sufficient to support modem data transmission rates (such as 10 Gbps OC-192, whose rates require 40 ns per operation). This calculation does not even consider the time needed to update the data structure, which could potentially add another 64 ns per packet.
Therefore, a need remains for an improved interval location algorithm for performing fast interval search and update operations. Due to the high cost per bit associated with such algorithms, it would also be desirable to minimize the amount of storage space required for storing a related data structure.